package com.desin.modle.datastruct.algo.linkedlist07;

import java.util.PriorityQueue;

public class Solution {
    public class ListNode {
     int val;
      ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

    public class Status implements Comparable<Status>{
        int value;
        ListNode pre;

        public Status(int value,ListNode pre){
            this.value=value;
            this.pre=pre;
        }

        @Override
        public int compareTo(Status status2){
            return this.value-status2.value;
        }
    }



    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0){
            return null;
        }
        PriorityQueue<Status> queue = new PriorityQueue<>();
        for(ListNode node:lists){
            queue.offer(new Status(node.val,node));
        }
        ListNode solider = new ListNode(0);
        ListNode cur = solider;
        while(!queue.isEmpty()){
            Status temp = queue.poll();
            cur.next=temp.pre;
            cur=cur.next;
            if(temp.pre.next!=null){
                queue.add(new Status(temp.pre.next.val,temp.pre.next));
            }
        }
        return solider.next;
    }
}
